package com.bascker.algorithm.practice.arr;

import java.util.Arrays;

/**
 * 航班预定: 差分数组技巧
 *
 * n 个航班，从 1 到 n 进行编号。有一份航班预定表，表中第 i 条预定记录 bookings[i] = [i, j, k],
 * 表示从 i 到 j 的每个航班上预定了 k 个座位。
 *
 * 请返回一个长度为 n 的数组 answer，按照航班编号顺序返回每个航班上预定的座位数。
 *
 * Note:
 * 1) 1 <= bookings.length <= 20000                        ==> 最多有 2W 条预定记录
 * 2) 1 <= bookings[i][0] <= bookings[i][1] <= n <= 20000  ==> 最多有 2W 个航班
 * 3) 1 <= bookings[i][2] <= 10000                         ==> 最多预定 1W 个座位
 *
 * For example:
 * <p>
 *     in:  bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
 *     out: [10,55,45,25,25]
 *
 * @apiNote from leetcode T1109
 */
public class BookFlight {

    public int[] corpFlightBookings(int[][] bookings, int n) {
        // 初始化: 所有航班初始预定座位数为 0
        int[] answer = new int[n];
        /*
         * 对于 answer 的差分数组: 初始时，所有元素间差值都是 0
         * 1. 由于航班是 1 开始编号的，因此 diff[1] 对于的是 answer[0], diff[n + 1] 对应的是 answer[n - 1, n] 的差值
         *    即 diff[1] = answer[0], diff[n + 1] = answer[n] - answer[n - 1]
         * 2. 原本 n + 1 就可以对于 answer 的, 为了防止 diff[j + 1] 出现数组越界，所以多给了一个位置 # Q1
         *    若 diff[j + 1] 处理时做边界处理，变为 j + 1 < n ? diff[j + 1] -= k, 就可以设置 n + 1
         */
        int[] diff = new int[n + 1];

        // 遍历预定表，构造差分数组
        Arrays.stream(bookings).forEach(booking -> {
            int i = booking[0];
            int j = booking[1];
            int k = booking[2];
            diff[i] += k;
            diff[j + 1] -= k;
        });

        // 根据差分数组构造 answer
        answer[0] = diff[1];
        for (int i = 1; i < n; i ++) {
            answer[i] = diff[i + 1] + answer[i - 1];
        }

        return answer;
    }

}
